package flare.analytics.cluster
{
  import flare.animate.Transitioner;
  import flare.util.math.IMatrix;
  import flare.vis.data.Data;
  import flare.vis.data.DataList;

  /**
   * Hierarchically clusters a set of items using agglomerative clustering.
   * This approach continually merges the most similar items (those with the
   * minimum distance between them) into clusters, until all items have been
   * merged into a final resulting cluster tree. Clients must provide a
   * distance function that takes as input two <code>DataSprite</code>
   * instances and returns a <code>Number</code>.
   * <p>This class supports both <i>minimum-link</i> clustering, in which the
   * distance between clusters is measured as the distance between the two
   * nearest items in each cluster, and <i>maximum-link</i> clustering, in
   * which distance is measured using the two furthest items in each cluster.
   * </p>
   * <p>For a richer description, see
   * <a href="http://en.wikipedia.org/wiki/Cluster_analysis#Agglomerative_hierarchical_clustering">
   * the Wikipedia article on Cluster Analysis</a>.
   * </p>
   */
  public class AgglomerativeCluster extends HierarchicalCluster
  {
    /** A function defining distances between items. */
    public var distance:Function = null;

    /** If true, minimum-link distances are computed between clusters.
     *  If false, maximum-link distances are computed between clusters. */
    public var minLink:Boolean = true;

    // --------------------------------------------------------------------

    /**
     * Creates a new agglomerative cluster instance
     */
    public function AgglomerativeCluster(group:String = Data.NODES)
    {
      this.group = group;
    }

    /** @inheritDoc */
    public override function operate(t:Transitioner = null):void
    {
      calculate(visualization.data.group(group), distance);
    }

    /**
     * Calculates the community structure clustering. As a result of this
     * method, a cluster tree will be computed and graph nodes will be
     * annotated with both community and sequence indices.
     * @param list a data list to cluster
     * @param d a distance function
     */
    public function calculate(list:DataList, d:Function):void
    {
      compute(list.distanceMatrix(d));
      _tree = buildTree(list);
      labelNodes();
    }

    /** Computes the clustering */
    private function compute(Z:IMatrix):void
    {
      _merges = new MergeEdge(-1, -1);
      _qvals = [];
      _size = Z.rows;

      var m:MergeEdge = _merges;
      var i:uint, j:uint, k:int, s:int, t:int, ii:uint, jj:uint;
      var min:Number, a:uint, b:uint, bb:uint, imax:int;
      var v:Number, sum:Number = 0, Q:Number = 0, Qmax:Number = 0, dQ:Number;

      // initialize matrix
      var N:int = Z.rows;
      var idx:/*int*/Array = new Array(N);

      for(i = 0; i < N; ++i)
      {
        idx[i] = i;
        Z.set(i, i, Number.POSITIVE_INFINITY);
      }

      // run the clustering algorithm
      for(var iter:int = 0; iter < N - 1; ++iter)
      {
        // find the nodes to merge
        min = Number.MAX_VALUE;

        for(ii = 0; ii < idx.length; ++ii)
        {
          i = idx[ii];

          for(jj = ii + 1; jj < idx.length; ++jj)
          {
            j = idx[jj];
            v = Z.get(i, j);

            if(v < min)
            {
              min = v;
              a = i;
              b = j;
              bb = jj;
            }
          }
        }
        i = a;
        j = b;
        jj = bb;

        // perform merge on graph
        for(k = 0; k < N; ++k)
        {
          if(minLink)
          {
            v = Math.min(Z.get(i, k), Z.get(j, k)); // min link
          }

          else
          {
            v = Math.max(Z.get(i, k), Z.get(j, k)); // max link
          }
          Z.set(i, k, v);
          Z.set(k, i, v);
        }

        for(k = 0; k < N; ++k)
        {
          Z.set(j, k, Number.POSITIVE_INFINITY);
          Z.set(k, j, Number.POSITIVE_INFINITY);
        }
        idx.splice(jj, 1);

        Q += min;

        if(Q > Qmax)
        {
          Qmax = Q;
          imax = iter;
        }
        _qvals.push(Q);
        m = m.add(new MergeEdge(i, j));
      }
    }
  } // end of class AgglomerativeCluster
}